package com.yaoli.niuke;

/**
 * Created by will on 2017/5/20.
 */
public class _01_bag {
    public static void main(String[] args) {
        int Volume = 10;
        int [] volme = {2,2,6,5,4};
        int [] value = {6,3,5,4,6};


        int [][] f = new int[volme.length+1][Volume+1];

        for(int i = 1; i <= volme.length ; i++){
            for(int j = 1; j <= Volume ; j++){
                if(volme[i - 1] <= j){
                    f[i][j] = Math.max(f[i-1][j],f[i-1][j-volme[i - 1]]+value[i - 1]);
                }else{
                    f[i][j] = f[i - 1][j];
                }
            }
        }

        System.out.println(f[volme.length][Volume]);
    }
}
